1. Field of the Invention
This invention relates to the field of computer systems employing non-volatile media. More specifically, this invention relates to a non-volatile cache for devices such as disk drives in a computer system.
2. Description Of the Related Art
Attempts are constantly made to increase the performance of modem computer systems. Typically, because input/output devices such as disk drives are slower than the circuitry in computer systems (such as central processing units and/or memory devices), attempts have been made to increase the performance of these I/O devices. However, because such devices are electromechanical in nature, there is a finite limit beyond which performance cannot be increased. Other methods and devices have thus been developed for reducing the I/O bottleneck in order to increase overall computer system performance.
Once way to reduce the information bottleneck for I/O devices such as a disk drives is to use a cache. A cache is a memory device which logically resides between a device and the remainder of the computer system such as a central processing unit(s) and/or computer bus. A cache is an area of memory which serves as a temporary storage area for the device (such as computer memory or a disk drive). Frequently accessed data resides in the cache after an initial access and a subsequent accesses to the same data will be made to the cache instead of the device. A cache for memory typically uses a higher speed type of memory, such as static memory, for the cache memory than the main computer system's memory, which is typically implemented in dynamic memory. A cache for a disk drive can generally reside in computer main memory, but may also reside in a separate device coupled to the system bus. One such system containing memory, a processor and fixed media devices (such as disk drives) used in conjunction with a cache is shown as system 100 in FIG. 1.
System 100 in FIG. 1 is a computer system with multiple disk drives 121 through 125. Computer system 100 comprises a bus 101 for communicating information between a processor 102 and devices such as main memory 104 and disk drives 121 through 125. Disk drives 121 through 125 are accessible via lines 110 coupled to bus 101, or, alternatively, through cache 120. As discussed previously, if a particular datum in one of the disks 121 through 125 is accessed that was read on a previous access, that location will reside in cache 120. The datum will be in the cache unless it has been replaced using the system's cache replacement or coherency algorithm. In the case of a "cache hit " (the data resides in the cache), the data will be retrieved directly from cache 120. In the case of a "cache-miss " (the data is not contained in cache 120), the information will be retrieved directly from the fixed media drive over lines 110 to bus 101. The data may be made available to processor 102, or alternatively loaded into main memory 104 in a direct memory access (DMA) system. In the event of a "cache-miss " the data will also be placed into cache 120 for later accesses.
Write operations are treated differently than reads. There are two basic methods for writing data to a cache: the "write-through " (or store-through) cache replacement algorithm; and the "write-back " (or copy back or store in) cache replacement algorithm. In a write-through replacement algorithm, every time a write is made the information is written to the cache and a simultaneous request is made on the bus to write the data to the fixed media device(s). Cache contents always remain consistent with the contents of the disk drive. In a "write-back " cache replacement algorithm, the information is written only to the cache. Logic in the computer system writes the cache block to the device only when the cache block is modified. In a write-back caching system, cache contents are considered "dirty " when they are inconsistent with the contents of fixed media device(s). If the cache contents are modified and the disk has not yet been updated from the cache, then the cache block is flagged as "dirty " indicating that it needs to be written to the disk. An area is typically reserved in a cache such as 120 to store information to indicate whether blocks stored in the cache are clean or dirty. This area is known as a cache "tag. " If a block is "dirty, " then the location is flagged using a status bit. The dirty block is written back to the disk at a time when the cache is idle, or when modified cache contents are to be replaced by new data. After writing the data back to the disk, the "dirty " bit is cleared. Under normal operating circumstances, a write-back cache substantially increases device and thus overall system performance as disk operations are performed only when absolutely necessary. However, if computer system power is lost while data contained in the cache is "dirty, " then the device will not be updated with current data. This may result in corruption of files stored on the disk, because certain allocation tables or other file linkage information stored on the device may not be complete prior to the computer system losing power. Also, data contained within cache 120 is irretrievably lost. The losing of system power while the cache contains "dirty " data is therefore to be avoided whenever possible to avoid data loss and file corruption on disk drives coupled to the computer system.
A typical prior art software architecture for controlling fixed media devices is shown in FIG. 2. 200 in FIG. 2 is representative of a software architecture used by a UNIX (UNIX is a trademark of AT&T Bell Laboratories of Murray Hill, N.J.) brand operating system. 200 comprises a device switch unit 201 which is responsible for directing logical device accesses to software drivers responsible for physical media devices coupled to the system. For example, one logical device driver 202 may be directed towards physical device driver driver A 210, thus controlling physical devices 121 and 122. A second logical device driver 203 may result in an access to a second physical device driver 211, and thus be directed towards physical medium 123. Numerous logical devices may be defined in prior art system 200, all accesses to particular logical devices being directed by device switch unit 201. Numerous logical devices may map to the same physical device unit(s). For instance, yet another logical device 204 represented in device switch unit 201 may be directed towards the same physical device driver A 210, and thus to physical media 121 and 122. Caching schemes as implemented by certain prior art systems are contained within the device driver(s) such as 210 and 211 shown in FIG. 2. The device drivers handle all read and write operations, whether to the cache device(s) or to the physical media themselves. Also, drivers 210 and 211 handle all write-back requests to the physical media at appropriate times, such as when data becomes "dirty " and when specified periods of time elapse under an LRU (least recently used) algorithm.
An alternative remedy to the loss of data contained in a volatile cache is the use of a battery to power the cache. If computer system power is lost, data contained within the cache is retained because memory continues to be powered by the battery. When system power is restored, the system resumes normal operation and valid data still resides in the cache waiting to be written-back to disk. This solution is dependent upon the battery having power to retain the memory in the cache for the duration of the system power loss. If the battery is exhausted during the interval when there is no system power, data contained in the cache will be lost. Because battery power is finite and memory circuits such as dynamic memory devices require refreshing at regular intervals (thus consuming power at a fairly high rate) special care must be taken that the battery has the capacity to retain the data for a worst case. Worst case failures cannot be absolutely anticipated, batteries sometimes suffer from reliability problems, resulting in premature failure and a system may be without power for a long period of time, so the loss of data in a battery-backed cache may still occur.
One prior method to avoid corruption of fixed media devices coupled to a computer system is that used by the UNIX brand operating system during the system power-up initialization process (or bootstrap). During a system bootstrap, all fixed media devices coupled to a UNIX brand system are scanned to determine whether any file allocation tables or file indices residing on each disk need to be restored. Incomplete files or file indices results in the inability of the system to read these files. If any file indices or other file linkage information is incomplete, then the system software repairs the indices and pointers for the files as best as can be approximated to prevent the file corruption. This process, however, consumes an inordinate amount of real-time during system bootstrap, because all sectors and tracks of allocated sections in fixed media devices coupled to the system must be scanned. Depending on how much storage is available on the system, such a fie verification process substantially increases the amount of time needed for system initialization even after losing power for only a short period of time. In an MS-DOS brand operating system, in contrast, where no such file verification process takes place, the loss of system power while "dirty " information is still contained in the cache will result in the corruption or inability of files and data loss in fixed media devices coupled to the system.